package com.duoduo.滑动窗口;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @program: algorithm
 * @description: 无重复字符的最长子串
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * @author: chaidl  ！
 * @create: 2022-03-18 15:10
 */
public class 无重复字符的最长子串 {
    //采用滑动窗口解决
    public int lengthOfLongestSubstring(String s) {
    //    首先判断字符串长度如果是1就直接返回
        int length=s.length();
        if (length<=1){
            return length;
        }
        int left=0,right = 0;
        int maxLength=1;
        Set<Character> window=new HashSet<>();
    //    当右边界出界的时候跳出循环
        while (right<length){
            char tmp=s.charAt(right);
            //如果窗口里面已经存在说明重复，要移除重复的字符串
            while (window.contains(tmp)){
                window.remove(s.charAt(left));
                left++;
            }
            maxLength=Math.max(maxLength,right-left+1);
            window.add(s.charAt(right));
            right++;
        }
        return maxLength;
    }
    public int lengthOfLongestSubstring2(String s) {
        //    首先判断字符串长度如果是1就直接返回
        int length=s.length();
        if (length<=1){
            return length;
        }
        int left=0,right = 0;
        int maxLength=1;
        Map<Character,Integer> window=new HashMap<>();
        //    当右边界出界的时候跳出循环
        while (right<length){
            char tmp=s.charAt(right);
            //拿到有指针字符的索引
            Integer rightIndex = window.getOrDefault(tmp, -1);
            //然后判断，如果是-1表示没重复，不是-1表示重复，left直接调到重复字符的下一个位置
            left=Math.max(left,rightIndex+1);
            maxLength=Math.max(maxLength,right-left+1);
            window.put(s.charAt(right),right);
            right++;
        }
        return maxLength;
    }
}
